package leetcode.editor.cn;

//[547]省份数量
public class NumberOfProvinces547 {
    public static void main(String[] args) {
        Solution solution = new NumberOfProvinces547().new Solution();
        int[][] isConnected = {
                {1,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
                {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
                {0,0,0,1,0,1,1,0,0,0,0,0,0,0,0},
                {0,0,0,0,1,0,0,0,0,1,1,0,0,0,0},
                {0,0,0,1,0,1,0,0,0,0,1,0,0,0,0},
                {0,0,0,1,0,0,1,0,1,0,0,0,0,1,0},
                {1,0,0,0,0,0,0,1,1,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,1,1,0,0,0,0,1,0},
                {0,0,0,0,1,0,0,0,0,1,0,1,0,0,1},
                {0,0,0,0,1,1,0,0,0,0,1,1,0,0,0},
                {0,0,0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,1,0,1,0,0,0,0,1,0},
                {0,0,0,0,0,0,0,0,0,1,0,0,0,0,1}
        };
        System.out.println("NumberOfProvinces547:main:"+ solution.findCircleNum(isConnected));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //并查集 执行耗时:1 ms,击败了97.56% 的Java用户 //	内存消耗:47 MB,击败了13.17% 的Java用户
        public int findCircleNumUnion(int[][] isConnected) {
            if (isConnected == null) return 0;
            int length = isConnected.length;
            if (length < 1) return 0;

            int[] parent = new int[length];
            //自己的根节点，是自己。
            for (int i = 0; i < length; i++) {
                parent[i] = i;
            }
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    if (isConnected[i][j] == 1) {
                        union(parent, i, j);
                    }
                }
            }

            //根节点的数量。独立的个数。
            int count = 0;
            for (int i = 0; i < parent.length; i++) {
                if (parent[i] == i) count++;
            }
            return count;
        }
        //合并。
        // 子接点都指向父节点,父节点指向跟节点。
        // 子接点都指向根节点。路径压缩。
        private void union(int[] parent, int i, int j) {
            int rooti = findRoot(parent, i);
            int rootj = findRoot(parent, j);
            parent[rooti] = rootj;//所有指向 根节点 i 的节点。再次指向了根节点 j.
        }

        private int findRoot(int[] parent, int i) {
            if (parent[i] != i) {//不是根节点。
                parent[i] = findRoot(parent, parent[i]);
                // parent[i] = root //路径压缩。都指向根节点。不指向父节点。
            }
            return parent[i];
        }


        //dfs  执行耗时:1 ms,击败了97.56% 的Java用户 //	内存消耗:46.8 MB,击败了48.95% 的Java用户
        public int findCircleNumDfs(int[][] isConnected) {
            if (isConnected == null || isConnected.length < 1
                    || isConnected[0] == null || isConnected[0].length < 1) return 0;
            int vistedCount = 0;

            //肯定是 m = n 活着 是 m ，n-1 只能相差 1 个否则，m m-1无法展示关系。 最后 1 个是 m *m
            int len = isConnected.length;
            //dfs 重点
            int[] isVisitedCity = new int[len];
            for (int i = 0; i < len; i++) {//fori 所有 city
                if (isVisitedCity[i] == 1) continue;
                vistedCount++;
                //遍历，相邻的 city
                mdfs(isConnected, isVisitedCity, i);
            }
            return vistedCount;
        }
        private void mdfs(int[][] isConnected, int[] isVisitedCity, int curCity) {
            if (isVisitedCity[curCity] == 1) return;//找过的，stop.
            isVisitedCity[curCity] = 1;
            for (int i = 0; i < isConnected.length; i++) {//所有的 遍历。
                if (isConnected[i][curCity] == 1) {
                    mdfs(isConnected, isVisitedCity, i);//相邻，继续找相邻。
                }
            }
        }


        //并查集，单独的 class
        public int findCircleNum(int[][] isConnected) {
            if (isConnected == null || isConnected.length < 1
                    || isConnected[0] == null || isConnected[0].length < 1) return 0;

            int len = isConnected.length;
            UnionQuick unionQuick = new UnionQuick(len);
            for (int i = 0; i < len; i++) {
//                for (int j = 0; j < len; j++) {
                for (int j = i+1; j < len; j++) {//减少，不必要的遍历。
                    if (isConnected[i][j]==1){
                        unionQuick.union(i, j);
                    }
                }
            }

            return unionQuick.rootCount();
        }
        class UnionQuick {
            private final int[] parentNode;//有 n 个 root ,依次都合并。。。根据相关性
            private final int[] rank;//根结点的 rank ,一般指，深度。 虽然这个 不准确 而且会变。 查看 UnionFindDynamic
            //parentNode 数组，表示，所有的元素。
            // parentNode[i]-->val 表示 他爹 是 谁。 eg:1 的 爹是谁：  parentNode[1] = 1  or 2 。。。
            private int count;

            //init
            public UnionQuick(int n) {
                this.parentNode = new int[n];
                this.rank = new int[n];
                count = n;
                for (int i = 0; i < n; i++) {
                    parentNode[i] = i;// 自己的 -- 父节点 --自己。
//            rank[i]=0;def is 0
                }
            }

            //根节点。。 parentNode[k] = k .始祖，自己就是爹。
            public int findRoot(int i) {
                int tempRoot = i;
                //找到 root  tempRoot
                while (tempRoot != parentNode[tempRoot]) {//他爹，不是自己。。继续
                    //找到了 他爹，
                    tempRoot = parentNode[tempRoot];//继续找， tempRoot爹。
                }
                //路径压缩，
                // only 压缩 i 指向-->root
//        if (tempRoot != i) {
//            parentNode[i] = tempRoot;
//        }
                //压缩，所有的节点。这条线上的。。子节点
                while (i != tempRoot) {
                    int tempP = parentNode[i];
                    parentNode[i] = tempRoot;//所有的节点---》root.
                    i = tempP;
                }
                return tempRoot;
            }

            public void union(int p, int q) {
//                int proot = parentNode[p];
//                int qroot = parentNode[q];
                int proot = findRoot(p);
                int qroot = findRoot(q);
                if (proot != qroot) {
                    if (rank[proot] > rank[qroot]) {
                        parentNode[qroot] = proot;
                    } else if (rank[proot] < rank[qroot]) {
                        parentNode[proot] = qroot;
                    } else {
                        parentNode[proot] = qroot;
                        rank[qroot] += 1;
                    }
                    count--;//不需要单独统计了。
                }
            }

            public int rootCount() {
//                int count = 0;
//                for (int i = 0; i < parentNode.length; i++) {
//                    if (parentNode[i] == i) {
//                        count++;
//                    }
//                }
                return count;
            }
        }

    }


//leetcode submit region end(Prohibit modification and deletion)

}